// 题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
/**
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 */

/**
 * 思路1
 * 初始化一个最小值变量，它的初始值可以设一个非常大的数（比如 Infinity），
 * 然后开始遍历整个栈。在遍历的过程中，如果遇到了更小的值，就把最小值变量更新为这个更小的值。
 * 这样遍历结束后，我们就能拿到栈中的最小值了。
 * 这个过程中，我们对栈进行了一次遍历，时间复杂度无疑是 O(n)。
 */

/**
 * 初始化你的栈结构
 */
const MinStack = function () {
  this.stack = [];
};

// 栈的入栈操作，其实就是数组的 push 方法
MinStack.prototype.push = function (x) {
  this.stack.push(x);
};

// 栈的入栈操作，其实就是数组的 pop 方法
MinStack.prototype.pop = function () {
  this.stack.pop();
};

// 取栈顶元素，咱们教过的哈，这里我本能地给它一个边界条件判断（其实不给也能通过，但是多做不错哈）
MinStack.prototype.top = function () {
  if (!this.stack || !this.stack.length) {
    return;
  }
  return this.stack[this.stack.length - 1];
};

// 按照一次遍历的思路取最小值
MinStack.prototype.getMin = function () {
  let minValue = Infinity;
  const { stack } = this;
  for (let i = 0; i < stack.length; i++) {
    if (stack[i] < minValue) {
      minValue = stack[i];
    }
  }
  return minValue;
};

/***思路2
 * 我们可以考虑再搞个栈（stack2）出来作为辅助，让这个栈去容纳当前的最小值。
 * 如何确保 stack2 能够确切地给我们提供最小值？ 这里我们需要实现的是一个从栈底到栈顶呈递减趋势的栈
 * 1. 取最小值：由于整个栈从栈底到栈顶递减，因此栈顶元素就是最小元素。
 * 2. 若有新元素入栈：判断是不是比栈顶元素还要小，否则不准进入 stack2。
 * 3. 若有元素出栈：判断是不是和栈顶元素相等，如果是的话，stack2 也要出栈。
 */

 const MinStack2 = function() {
    this.stack = [];
    // 定义辅助栈
    this.stack2 = [];
};

MinStack2.prototype.push = function(x) {
    this.stack.push(x);
    // 若入栈的值小于当前最小值，则推入辅助栈栈顶
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
        this.stack2.push(x);
    }
};

MinStack2.prototype.pop = function() {
    // 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
    if(this.stack.pop() == this.stack2[this.stack2.length-1]){
        this.stack2.pop();
    }
};

MinStack2.prototype.top = function() {
    return this.stack[this.stack.length-1];
};

MinStack2.prototype.getMin = function() {
    // 辅助栈的栈顶，存的就是目标中的最小值
    return this.stack2[this.stack2.length-1];
};
// const stack = new MinStack
const stack = new MinStack2
stack.push(-2)
stack.push(3)
stack.push(2)
console.log(stack.getMin());
